package day_2022_12_to_3.day;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

/**
 * @author haomin
 * @date 2022/12/08 23:20
 **/
public class Day12_8_Review {
    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if(matrix.length == 0 || matrix[0].length == 0) return false;
            int m = matrix.length, n = matrix[0].length, r = 0, c = n-1;
            while(r < m && c >= 0) {
                if(target > matrix[r][c]) r++;
                else if(target < matrix[r][c]) c--;
                else return true;
            }
            return false;
        }
    }
    class Solution2 {
        public int[] reversePrint(ListNode head) {
            if(head == null) return new int[0];
            Deque<Integer> s = new LinkedList<>();
            while(head != null) {
                s.push(head.val);
                head = head.next;
            }
            return s.stream().mapToInt(Integer::intValue).toArray();
        }
    }

    class Solution3 {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeHelper(preorder, inorder, 0, inorder.length-1);
        }
        int i = 0;
        public TreeNode buildTreeHelper(int[] pre, int[] in, int l, int r) {
            if(i == pre.length) return null;
            if(l > r) return null;
            TreeNode cur = new TreeNode(pre[i]);
            i++;
            int ind = findInd(in, cur.val);
            cur.left = buildTreeHelper(pre, in, l, ind-1);
            cur.right = buildTreeHelper(pre, in, ind+1, r);
            return cur;
        }
        public int findInd(int[] in, int val) {
            for(int i = 0; i < in.length; ++i) {
                if(in[i] == val) return i;
            }
            return -1;
        }
    }
}